iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 17
0
Security

無趣的密碼學,有趣的加密!系列 第 17

[Day 17] 017 - 橢圓曲線密碼學 - Elliptic Curve Cryptograph (二)

  • 分享至 

  • xImage
  •  

橢圓曲線密碼學 - Elliptic Curve Cryptograph (二)

這邊會展示的程式碼,是不能拿來做正式加解密的。

我先註明一下,因為時間不是很夠了,無法研究一些特殊的曲線跟算法。

所以這邊只能拿出最基本的,實驗且娛樂性質的程式。

當取模的數有點大時,整個加密系統幾乎跑不太動。

當然,這並沒有做類似於X25519那樣的曲線特化。

因此如果未來有時間有機會,會再寫幾篇真正能像RSA那樣隨意調整長度的程式。

這邊就是講解除和去編寫一些程式碼,讓上一章講的東西實現而已。

再一次聲明,這個不是安全曲線、不是有效的程式、比起我寫完的RSA還要慢上超級無敵多。

無法體現出ECC的優秀,但能展示ECC的一些方法。


程式講解

首先我們的第一步就是讓大家輸入a、b、mod,並確認是否符合橢圓曲線的規則。

判斷是否符合單一解的橢圓曲線公式:(4 * (a^3) + 27 * (b^2)) (mod n) == 0

def get_arg(lens:int) -> Tuple[int, int, int]:
    while True:
        a = int(input('a:'))
        b = int(input('b:'))
        mod = get_prime(lens)
        if (4 * (a ** 3) + 27 * (b ** 2)) % mod == 0:
            print('Is not correct number.')
        else:
            break
    return a, b, mod

get_prime請看RSA那邊的程式。
生成大質數的一個Function。

接著我們必須先把R=Q+P的公式寫成function。

還記得公式嗎:

  1. 要是 xp==xq 而且 yp == yq則:S為(3*Xp^2 - a)/(2*Yp) (mod K)

  2. 要是 xp!=xq 則:S為(Yp-Yq)/(Xp-Xq) (mod K)

  3. 但為了方便,我們把分子跟分母先分開。

  4. 要是xp!=xq 則確認是否有負號,要是有將負號紀錄起來,將分子跟分母都先取絕對值。

  5. 接著做gcd取得最大公因數,然後分子分母同除以最大公因數。

  6. 最後將分母變成倒數形式,並先做模處理防止有小數。

  7. 分子跟倒數後的分母兩者相乘並乘以負號後紀錄,取得兩點的斜率並取模,最後回傳R點或稱為G點(代號的不同)。

def get_q(p: Tuple[int, int], q: Tuple[int, int], a: int, mod: int) -> Tuple[int, int]:
    def get_s(p: Tuple[int, int], q: Tuple[int, int], a: int, mod: int) -> int:
        negative = 1
        if p == q:
            numerator = 3 * (p[0] ** 2) + a
            denominator = 2 * p[1]
        else:
            numerator = q[1] - p[1]
            denominator = q[0] - p[0]
            if numerator < 0 or denominator < 0:
                negative = -1
                numerator = abs(numerator)
                denominator = abs(denominator)
        gcd = get_gcd(numerator, denominator)
        numerator = numerator // gcd
        denominator = denominator // gcd
        # Get reciprocal
        reciprocal = get_reciprocal(denominator, mod)
        return (negative*numerator * reciprocal) % mod

    s = get_s(p, q, a, mod)
    xr = (s**2-p[0]-q[0]) % mod
    yr = (s*(p[0]-xr) - p[1]) % mod
    return xr, yr


完成了計算兩點之後,我們就必須先選一個點來當作基點。

因此隨機選擇一個數值來當G點。

而G點也必須符合橢圓曲線上的點。

判斷是否在曲線上:y^2 (mod n) == x^3+x*a+b (mod n)


def get_point(a: int, b: int, mod: int, lens: int) -> Tuple[int, int]:
    while True:
        x = random.randint(10**(lens-1), 10**lens-1)
        for _ in range(100):
            y = random.randint(10**(lens-1), 10**lens-1)
            if (y ** 2 % mod) == ((x**3+x*a+b) % mod):
                print(9)
                return x, y

並且要知道這個G點跟取餘數之後最大的n點。
利用不斷的做兩點堆疊從G、2G、3G...nG。

def get_g_n(g: Tuple[int, int], a: int, mod: int) -> int:
    symmetry_y = (-1*g[1]) % mod
    temp = g
    n = 0
    while True:
        n += 1
        temp = get_q(temp, g, a, mod)
        if g[0] == temp[0] and symmetry_y == temp[1]:
            return n

這下我們檢視一下現有的參數:

  • 橢圓曲線相關:a、b
  • 有限域:mod
  • 基點:G
  • 此基點的最大階:n

接下來就簡單了。
還記得我說的吧?
我們很難從AG或BG跟G得知A或B。

那我們先選一個A然後算出它的AG。
再用同樣方法隨機選一個B,然後算出它的BG。

程式很簡單地在0到n(此基點的最大階)中挑一個來當作私鑰。
然後算出公鑰。

def get_xg(g: Tuple[int, int], xg: Tuple[int, int], x: int, a: int, mod: int) -> Tuple[int, int]:
    temp = xg
    while x != 1:
        temp = get_q(temp, g, a, mod)
        x -= 1
    return temp

def gen_key(g: Tuple[int, int], n: int, a: int, mod: int) -> Tuple[int, Tuple[int, int]]:
    private_key = random.randint(0, n)
    public_key = get_xg(g,g, private_key, a, mod)
    return private_key, public_key

這樣就可以得到(A,AG,G)跟(B,BG,G),然後兩者交換後驗證是否能得到共同的ABG。
然後其他的流程如下:

def eccdh():
    lens = int(input('金鑰長度:'))
    a, b, mod = get_arg(lens+1)
    g, n = gen_g(a, b, mod, lens)
    a_private, a_public = gen_key(g, n, a, mod)
    b_private, b_public = gen_key(g, n, a, mod)

    # check ABG
    apbp = get_xg(g,a_public, b_private, a, mod)
    bpap = get_xg(g,b_public, a_private, a, mod)

    if apbp != bpap:
        print("APBP Is Not Equal:", apbp, bpap)
        return False

其他程式


def get_gcd(a: int, b: int) -> int:
    return a if b == 0 else get_gcd(b, a % b)

def get_reciprocal(value: int, mod: int) -> int:
    for i in range(1, mod):
        if (i * value) % mod == 1:
            return i
    return -1

附上程式碼


橢圓曲線密碼學 結論

這邊我很慚愧的跟大家說,這個程式不像之前的RSA之類的,能真的寫出來並使用。

這邊其實是用便利的方式來算出xG的……其實不能這樣(這樣會簡單的被反推或驗證,而且速度太慢)。

而且想講的X25519曲線特性也沒機會講,我會先提供我所有的資料在補充資料裡面。

裡面其實很詳細地介紹了X25519的優勢,但沒能完全理解並實現其算法還是有點難過的。

但不用擔心,我會找時間寫幾篇文章來處理這部份,唯一的缺點就是不連貫而已。

本來想說花時間將X25519的演算法處理完,但後來一看裡面太多新的數學知識了。

例如Edwards曲線、蒙哥馬利曲線、蒙哥馬利階梯等等的。

無法完整地討論整個ECC我自己也很慚愧,要是能完整地討論這一部份,這系列的文章將會是很先進的密碼學類文章了。

還有很多關於ECC的算法都沒有介紹……有機會一定跟大家來說說。

如果到時候有做新的文章更新,或是大神有寫文章,我會放在留言或編輯後,放在最下面。

接下來就是Hash的部分了。


參考資料

橢圓曲線加密演算法

椭圆曲线加密算法(ECC)


補充資料

Curve25519 TW WiKi

Curve25519 US WiKi

深入理解 X25519

Ed25519: high-speed high-security signatures

RFC7748

Elliptic Curve Cryptography (ECC) - Concepts


上一篇
[Day 16] 016 - 橢圓曲線密碼學 - Elliptic Curve Cryptograph (一)
下一篇
[Day 18] 018 - 雜湊 - Hash (前言)
系列文
無趣的密碼學,有趣的加密!30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言